package 算法面试;

import java.util.ArrayList;
import java.util.List;

public class 单词搜索II {

    private TrieNode root;
    private int xLength;
    private int yLength;
    private List<String> exist;

    public static void main(String[] args) {
        char[][] board = {{'b', 'b', 'a', 'a', 'b', 'a'}, {'b', 'b', 'a', 'b', 'a', 'a'}, {'b', 'b', 'b', 'b', 'b', 'b'}, {'a', 'a', 'a', 'b', 'a', 'a'}, {'a', 'b', 'a', 'a', 'b', 'b'}};

        String[] words = {"abbbababaa"};
        单词搜索II a = new 单词搜索II();
        System.out.println(a.findWords(board, words));
    }

    public List<String> findWords(char[][] board, String[] words) {
        root = new TrieNode();
        exist = new ArrayList<String>();
        yLength = board.length;
        xLength = board[0].length;


        List<String> result = new ArrayList<String>();
        for (String word : words) {
            if (findWord(board, word)) {
                result.add(word);
            }
        }
        return result;
    }

    public boolean findWord(char[][] board, String word) {
        TrieNode node = root;
        for (int y = 0; y < board.length; y++) {
            char[] chars = board[y];
            for (int x = 0; x < chars.length; x++) {
                buildTrie(board, x, y, word);
            }
        }

        for (char c : word.toCharArray()) {
            if (node.containsKey(c)) {
                node = node.get(c);
            } else {
                return false;
            }
        }
        return true;
    }


    public void buildTrie(char[][] board, int x, int y, String word) {
        exist.clear();
        TrieNode node = root;
        char c = board[y][x];
        char findChar = word.charAt(0);
        if (c == findChar) {
            TrieNode newNode;
            if (node.containsKey(c)) {
                newNode = node.get(c);
            } else {
                newNode = new TrieNode();
                node.put(c, newNode);
            }
            exist.add(x + "," + y);
            buildTrie(board, x, y, newNode, -1, word, 1);
        }
    }

    //0：上，1：下，2：左，3：右
    public void buildTrie(char[][] board, int x, int y, TrieNode node, int direction, String word, int charAt) {
        if (charAt >= word.length()) {
            return;
        }

        TrieNode newNode;
        char findChar = word.charAt(charAt);
        //上
        if (!exist.contains(x + "," + (y - 1)) && direction != 1 && y - 1 >= 0) {
            char c = board[y - 1][x];
            if (c == findChar) {
                if (node.containsKey(c)) {
                    newNode = node.get(c);
                } else {
                    newNode = new TrieNode();
                    node.put(c, newNode);
                }
                exist.add(x + "," + (y - 1));
                buildTrie(board, x, y - 1, newNode, 0, word, charAt + 1);
                exist.remove(x + "," + (y - 1));
            }
        }
        //下
        if (!exist.contains(x + "," + (y + 1)) && direction != 0 && y + 1 < yLength) {
            char c = board[y + 1][x];
            if (c == findChar) {
                if (node.containsKey(c)) {
                    newNode = node.get(c);
                } else {
                    newNode = new TrieNode();
                    node.put(c, newNode);
                }
                exist.add(x + "," + (y + 1));
                buildTrie(board, x, y + 1, newNode, 1, word, charAt + 1);
                exist.remove(x + "," + (y + 1));
            }
        }
        //左
        if (!exist.contains((x - 1) + "," + y) && direction != 3 && x - 1 >= 0) {
            char c = board[y][x - 1];
            if (c == findChar) {

                if (node.containsKey(c)) {
                    newNode = node.get(c);
                } else {
                    newNode = new TrieNode();
                    node.put(c, newNode);
                }
                exist.add((x - 1) + "," + y);
                buildTrie(board, x - 1, y, newNode, 2, word, charAt + 1);
                exist.remove((x - 1) + "," + y);
            }
        }
        //右
        if (!exist.contains((x + 1) + "," + y) && direction != 2 && x + 1 < xLength) {
            char c = board[y][x + 1];
            if (c == findChar) {

                if (node.containsKey(c)) {
                    newNode = node.get(c);
                } else {
                    newNode = new TrieNode();
                    node.put(c, newNode);
                }
                exist.add((x + 1) + "," + y);
                buildTrie(board, x + 1, y, newNode, 3, word, charAt + 1);
                exist.remove((x + 1) + "," + y);
            }
        }

    }


}
